%The Challenge on Generating Instructions in Virtual Environments (GIVE; Koller et
%al.~\cite{KolStrGarByrCasDalMooObe10}) is a shared task in which natural language
%generation systems must generate real-time instructions that guide a user in a
%virtual world.  

The instruction giving task that we use to evaluate our approach is the GIVE
task~\cite{GarGarKolStr10}. In this task, the IF is situated in a 3D maze and the IG 
gives him directions in order to win a treasure hunt game. The
maze is composed of corridors and rooms connected with doors. It also
contains alarms which cause the IF to lose the game if he steps on them, and
objects such as plants, tables, chairs, etc that simulate the interior of a house. In order to win the game, the IF has to manipulate objects in the world, for example, he has to 
open doors, deactivate alarms, and press certain buttons to open the combination of a safe. The IG 
has information, such as how to desactivate
certain alarms, which is necessary to complete the task and the IF ignores. Hence, 
they need to collaborate to solve the task successfully. The GIVE task was originally designed as a shared task for comparing different strategies for giving effective and engaging instructions inside a game; inspired in traditional experiments such as Maptask~\cite{Anderson91}.   

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=.7\linewidth]{images/give-3D.jpg} 
\end{center}
%\vspace*{-5mm}
\caption{The IF view of the virtual environment when receiving the instruction ``Push a red button'' from the instructor. \label{give}}
\end{figure}
%\vspace*{-2mm}

The GIVE framework includes a 3D client that renders the house for the IF and a
chat-like interface for the IG to send text messages that are displayed on top of the
client window as shown in Fig.~\ref{give}. The IG can both see the map
from top view but also the first person view of the IF. The framework logs the position, the
orientation of the player and all the objects he can see every 200 milliseconds.
It also logs all objects manipulations. Such logging capabilities are not unique to GIVE, most multiplayer online game engines (MOGE) such as World of Warcraft and CounterStrike  offer a logging capability that provides the required capturing interface (in the gaming community, this is known as “replay”). 
MOGE also offer a chat-like interface for players and a top-view map to see the location of the other players. So our techniques are directly applicable to these virtual worlds with no added cost. 

The techniques developed for GIVE not only transfer to game like situations but to 
other navigation tasks such as pedestrian navigation and mixed reality navigation. They have been user in applications for pedestrian navigation such 
as GRUVE~\cite{janarthanam-lemon-liu:2012:Demo,avalos-benotti:2014} and virtualizations of real environments INIXIA~\cite{luna-benotti:2014}. The task of the virtual instructor in GRUVE is to assist a IF navigating 
through the streets of a city on Google Streetview. The challenge here is to generate instructions in the context of uncertain user positioning information and to adapt them to a user's experience in the neighborhood. 

In order to apply the annotation and selection algorithms to a particular task,
one needs both to provide a planning domain for that task, and a planner or pathfinding method, that is a method to calculate the plan that solves the task from whichever state the user and the enviroments are in. In GIVE, the
planner, LazyFF, is a Java implementation of the classical planner
FF~\cite{hoffmann01} and the planning domain is a standard PDDL representation of
the actions that are possible in the GIVE environments (see~\cite{hsu06} for description of
PDDL). Both the planner and the planning domain are freely available on the
web\footnote{\url{http://www.give-challenge.org/}}. We show an example of an
action within the PDDL domain used by GIVE in Figure~\ref{fig:pddl-example}: the
\emph{move} action requires two parameters, the \emph{from} and \emph{to}
positions. The preconditions are that the player is at \emph{from} position, that
\emph{to} position is adjacent to \emph{from} and that it is not blocked nor
alarmed. The effect of this action is to remove the player from the position \emph{from}
and locate him in the position \emph{to}.

\begin{figure}[!ht]
\footnotesize
\begin{verbatim}
(:action move
      :parameters (?from - position ?to - position)
      :precondition (and (player-position ?from) 
                    (adjacent ?from ?to non-blocked-state) 
                    (alarm-state ?to non-alarmed-state))
      :effect (and (not (player-position ?from)) (player-position ?to)))
\end{verbatim}
\normalsize
\caption{Example of a PDDL action}
\label{fig:pddl-example}
\end{figure}

The properties of the objects in the virtual world, such as buttons or alarms, are automatically updated in real time when actions are performed on the virtual world. 
The planning objects that are not directly extractable from the virtual world are the different positions that an IF can be in. These positions are infinite and need to be organized by space discretization in order for a  planner to be able to handle them. 
Space discretization is the problem of finding a partition of space such
that two disjoint regions are adjacent if they are accessible from each other
without obstacles in-between. Several techniques are used in games to
automatically build a space partition from a 3D world, which is useful for
pathfinding, and in our case for planning.  This partition, called a navigation
mesh can be built with triangulation methods based on the sweep-line algorithm or
divide and conquer methods, see~\cite{Chazelle1994} for a review. In GIVE, we can
however take advantage of the particular configuration of the worlds in which
corners are always ninety degrees. The partitioning algorithm works
in two steps. It first builds a set of overlapping regions by splitting rooms in
rectangular regions, creating regions for each interactive object in the world (e.g., the buttons).
For each pair of regions ($R_1$, $R_2$) that overlap, it then creates a new
region $R_3$ covering the overlap and subtracts it from $R_1$ and $R_2$. The
resulting set of regions is thus a partition of the world. This algorithm is
implemented in the GIVE framework, and an example of its application is shown in
Fig.~\ref{fig:discretization}. Each region marked in the figure is a position in the planning representation. 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=9cm]{images/give-discretized.png}
\end{center}
\caption{Sample discretization of a GIVE world}
\label{fig:discretization}
\end{figure}

